﻿using Autodesk.AutoCAD.Geometry;
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ClassLibrary1.Model
{
    public class DijkstraAlgorithm
    {
        public static Dictionary<Point3d, double> FindShortestPaths(Graph graph, Point3d start)
        {
            // 用于存储每个节点的最短路径距离
            var distances = new Dictionary<Point3d, double>();

            // 优先队列，用于存储待处理节点和其当前已知的最短距离
            var priorityQueue = new SortedSet<(double Distance, Point3d Vertex)>(Comparer<(double, Point3d)>.Create((a, b) =>
            {
                int compare = a.CompareTo(b);
                return compare == 0 ? a.ToString().CompareTo(b.ToString()) : compare;
            }));

            // 初始化所有节点的距离为正无穷大，起点的距离为0
            foreach (var vertex in graph.AdjacencyList.Keys)
            {
                distances[vertex] = double.MaxValue;
            }

            distances[start] = 0;
            priorityQueue.Add((0, start));

            // 处理优先队列中的节点
            while (priorityQueue.Count > 0)
            {
                var (currentDistance, currentVertex) = priorityQueue.Min;
                priorityQueue.Remove(priorityQueue.Min);

                // 遍历当前节点的所有相邻节点
                foreach (var (neighbor, weight) in graph.AdjacencyList[currentVertex])
                {
                    double distance = currentDistance + weight;

                    if (distance < distances[neighbor])
                    {
                        // 如果发现更短的路径，更新距离并重新插入优先队列
                        priorityQueue.Remove((distances[neighbor], neighbor));
                        distances[neighbor] = distance;
                        priorityQueue.Add((distance, neighbor));
                    }
                }
            }

            return distances;
        }
    }
}

